Many applications and devices rely on embedded cryptographic systems to provide security for an application and its associated data. These cryptosystems are often targets of individuals attempting to gain access to the applications or devices themselves or attempting to gather information being used by the applications (e.g., credit card numbers, cryptographic keys, etc.). Early attacks on cryptosystems focused on the weaknesses of cryptographic algorithms. For example, in plaintext attacks, attackers feed known plaintext into a cryptosystem and analyze the generated ciphertext to gather information about the cryptographic algorithm being used.
As the industry developed countermeasures against these algorithm attacks, a different style of attack emerged that focused on the physical implementation of cryptosystems. Referred to as side channel attacks (SCA), these attacks attempt to derive information about the internal state of a cryptosystem by monitoring its physical characteristics such as timing, instantaneous or static power consumption, electromagnetic radiation, and perhaps others that have yet to be discovered. This “leaking” information can present a major security threat to systems performing cryptographic operations if, for example, the cryptographic key may be extracted from the leaking information derived using the side-channel attacks.
While effective SCA countermeasures are well known, they are difficult to test and verify for effectiveness. This is typically done using penetration testing: attacking an actual system incorporating a countermeasure to see if the attack difficulty increases. There are several disadvantages to this approach. First, it requires side-channel collection equipment, specific tools for each target hardware platform, and expertise to collect and analyze the data. Second, the results are often inconsistent due to the myriad parameters that can drastically affect the test results. These include the skill and experience of the tester/attacker, the choice of side-channel, environmental conditions (e.g., temperature and background electromagnetic noise), data collection equipment, and analysis techniques used. Even highly-experienced testers cannot guarantee that all potential vulnerabilities will be identified because new attacks and analysis techniques are constantly emerging. Finally, penetration testing cannot evaluate individual software or hardware countermeasures because it is difficult to isolate the effects of one from the other when studying the system as a whole.
Software based tools have been developed for evaluating SCA countermeasures. For example, Bai et al., “A power analysis attack software simulation platform design and its applications,” 2010 2nd International Conference on Computer Engineering and Technology, vol. 6, 2010, proposed the use of hardware simulation tools to quickly evaluate hardware designs for differential power analysis (DPA) vulnerabilities by generating simulated power traces rather than collecting from real hardware. Bayrak et al., “A first step towards automatic application of power analysis countermeasures,” Proceedings of the 48th Design Automation Conference, ACM, 2011, pp. 230-35, available at http://doi.acm.org/10.1145/2024724.2024778, outlined an analysis technique based on mutual information that could be used to identify vulnerable instructions by mapping samples from real power traces to their corresponding instructions. This work represented the first method that significantly deviated from penetration testing and could therefore be applied in a semi-automated manner. However, this approach still required real side-channel traces and was, therefore, hampered by all the challenges that arise from collecting side-channel data (as discussed above). Additionally, it relied on the ability to map each sample of side-channel data to the software instruction that was being executed during that time. This mapping can be challenging depending on the underlying hardware and software stack.
Other works have eliminated the need for side-channel traces by performing the analysis solely on the dataflow graph of the target program. For example, Bayrak et al., “Sleuth: Automated verification of software power analysis countermeasures,” Cryptographic Hardware and Embedded Systems—CHES 2013, ser. Lecture Notes in Computer Science, G. Bertoni and J.-S. Coron, Eds. Springer Berlin Heidelberg, 2013, vol. 8086, pp. 293-310. available at http://dx.doi.org/10.1007/978-3-642-40349-1 17, presents a tool, called “Sleuth,” that converts the intermediate representation (IR) of a target program to a data-flow graph, and then uses that graph to generate satisfiability (SAT) queries. These queries can be solved with an SAT solver to detect unmasked intermediate values that may be exploited in a side-channel attack.
Eldib et al., “QMS: Evaluating the side-channel resistance of masked software from source code,” Proceedings of the The 51st Annual Design Automation Conference on Design Automation Conference, ser. DAC '14. New York, N.Y., USA: ACM, 2014, pp. 209:1-209:6. available at http://doi.acm.org/10.1145/2593069.2593193, showed that intermediate values could be partially masked and still leak information. Bayrak's Sleuth does not detect vulnerabilities related to partial or biased masking, so to address this limitation, Eldib proposed a technique for computing “quantitative masking strength” (QMS) to give a numerical score to the side-channel resistance of a countermeasure implementation.
Sleuth and QMS represent progress in automated SCA evaluation, however, both are limited in the type of leakages that they are designed to detect, and the type of programs that they are designed to analyze. The first limitation is largely due to analyzing the target program at the IR-level. Since the IR represents the program at an intermediate stage of compilation, an analysis on the IR cannot detect any vulnerabilities that may be introduced during the final stages of compilation. While previous developments have asserted that these final stages cannot generate vulnerable machine-code from protected IR, this is not true. The second limitation, which is due to the conversion of the program to a data flow graph, is that the target program must be transformed into a straight-line program that is free from conditional branches. This process involves modifying the program by loop unrolling, function in-lining, and other transformations that could potentially introduce or eliminate vulnerabilities. If any of these modifications are made to the target binary, the analysis results may not reflect the true security of the fielded system.
Effective software countermeasures against SCA are well known in theory, but in practice are difficult to implement properly due to issues such as unexpected compiler transformations and/or platform-specific leakage sources. Although several examples show that SCA is increasingly simple and inexpensive to perform as an attacker, evaluating the security of a system against SCA can still be expensive and time-consuming. Furthermore, most evaluation techniques must be performed near the end of the development schedule which adds significant risk. For example, as shown in the software development cycle (100) of FIG. 1, a software application with encryption and countermeasures is designed (101) and then implemented in code (102). The device on which the software is to be run is built and integrated with the implemented code (104). Only then is SCA security testing (106) performed. If unacceptable SCA vulnerabilities are detected (108), the process must return to the implementation step (102) followed by repetition of the build and integrate steps. This repetition can be costly and time consuming.
Accordingly, there is a need for a method of testing software for SCA vulnerabilities in a fast, inexpensive, and automated manner. The method should be able to be applied to evaluate software-based SCA countermeasures without access to source code and without the use of side-channel collection equipment.